//https://leetcode.cn/problems/5TxKeK/description/?envType=daily-question&envId=2024-02-01


class Solution {
public:
    vector<int> numsGame(vector<int> &nums) {
        const int MOD = 1'000'000'007;
        vector<int> ans(nums.size());
        priority_queue<int> left; // 维护较小的一半，大根堆
        priority_queue<int, vector<int>, greater<int>> right; // 维护较大的一半，小根堆
        long long left_sum = 0, right_sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            int b = nums[i] - i;
            if (i % 2 == 0) { // 前缀长度是奇数
                if (!left.empty() && b < left.top()) {
                    left_sum -= left.top() - b;
                    left.push(b);
                    b = left.top();
                    left.pop();
                }
                right_sum += b;
                right.push(b);
                ans[i] = (right_sum - right.top() - left_sum) % MOD;
            } else { // 前缀长度是偶数
                if (b > right.top()) {
                    right_sum += b - right.top();
                    right.push(b);
                    b = right.top();
                    right.pop();
                }
                left_sum += b;
                left.push(b);
                ans[i] = (right_sum - left_sum) % MOD;
            }
        }
        return ans;
    }
};